
/*
记忆化搜索
连接:https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/
题目:矩阵中的最长递增路径

 

   
*/

///记忆化搜索
class Solution {
public:
    int m ,n;
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};
    int memo[201][201];
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int ret=0;
        m = matrix.size();
        n = matrix[0].size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                ret = max(ret,dfs(matrix,i,j));
            }
        }
        return ret;
    }

    int dfs(vector<vector<int>>& matrix,int i,int j)
    {
        if(memo[i][j]!=0) return memo[i][j];
        int ret=1;
        for(int k=0;k<4;k++)
        {
            int x = dx[k]+i;
            int y = dy[k]+j;

            if(x>=0 &&  x<m && y>=0 && y<n && matrix[x][y]>matrix[i][j])
            {
                ret = max(ret,dfs(matrix,x,y)+1);
            }

        }
        memo[i][j] = ret;
        return ret;
    }
};